A RE-TRIANGULATION ALGORITHM IN 3D BUILDING GENERALIZATION

L. Ge, F. Wu, R. Zhai, P. Wang

Institute of Surveying and Mapping,Cartography and Geographical Infomation Engineering, Zhengzhou, China

graylln@yahoo.com.cn

3D building generalization is important in 3D generalization and it will be widely used in 3D visualization, especially in 3D city model. Triangle is the base of 3D visualization; a re-triangulation algorithm is proposed to deal with the extra triangles in 3D building modeling and generalization. The algorithm includes two parts: an outline finding algorithm based on neighboring triangle search and a triangulation algorithm of arbitrary polygon.

Triangles on one plane are the base of outline finding algorithm. Neighbors of all triangles are found and a way of noting line segment is introduced. Then search all triangles having less than three neighbors, add all border line segments to a point list (two points as one line segment) by the way introduced, order the line segments and merge those that are adjacent and collinear to get the plane outline. If more than one polygon is contained, the outline should be divided to proper number of polygons, which are used in the triangulation later.

Triangulation algorithm of arbitrary polygon is proposed by analyzing former algorithms on triangulation and based on the method of TIN triangulation. If the polygon has more than one ring, add two reverse line segments between rings to form one closed polygon. Two terms must be fulfilled in triangulation: 1center of triangle must lies inside polygon. 2 new edge of polygon can’t cut the borderline. Calculate two neighbor line segments and judge them by the terms above; if terms are fulfilled, one triangle is found and a new polygon comes forth. Repeat the step above and all triangles are found.

Experiments prove that the algorithm is easy, effective and available to all polygons, but the triangle’s shape is not always good, local optimizing method may be used to optimize the shape of triangles if necessary.